<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="libman.css">
<TITLE>
Examples
</TITLE>
</HEAD>
<BODY >
<A HREF="libman069.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman064.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc154">10.6</A>&nbsp;&nbsp;Examples</H2><UL>
<LI><A HREF="libman070.html#toc86">Interaction with Propagation</A>
<LI><A HREF="libman070.html#toc87">Repair Labeling</A>
</UL>

More examples of repair library use, in particular in the area
of local search, can be found in the <EM>Tutorial on Search Methods</EM>.<BR>
<BR>
<A NAME="toc86"></A>
<H3 CLASS="subsection"><A NAME="htoc155">10.6.1</A>&nbsp;&nbsp;Interaction with Propagation</H3>
<A NAME="@default401"></A>
In the following example, we set up three constraints as both repair and
fd-constraints (using the <B>r_conflict_prop</B> annotation) and
install an initial tentative assignment (using <B>tent_set</B>).
We then observe the result by retrieving the conflict sets:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
[eclipse 1]: lib(repair), lib(fd).             % libraries needed here
yes.
[eclipse 2]:
        fd:([X,Y,Z]::1..3),                    % the problem variables
        fd:(Y #\= X) r_conflict_prop confset,  % state the constraints
        fd:(Y #\= Z) r_conflict_prop confset,
        fd:(Y #=  3) r_conflict_prop confset,
        [X,Y,Z] tent_set [1,2,3],              % set initial assignment
        [X,Y,Z] tent_get [NewX,NewY,NewZ],     % get repaired solution
        conflict_constraints(confset, Cs),     % see the conflicts
        conflict_vars(Vs).

X = X{fd:[1..3], repair:1}
Y = 3
Z = Z{fd:[1, 2], repair:3}
NewX = 1
NewY = 3
NewZ = 3
Cs = [3 #\= Z{fd:[1, 2], repair:3}]
Vs = [Z{fd:[1, 2], repair:3}]

Delayed goals:
     ...
yes.
</PRE></BLOCKQUOTE>
Initially only the third constraint <CODE>Y #= 3</CODE> is inconsistent with the
tentative assignment. According to the definition of <B>r_conflict_prop</B>
this leads to
the constraint <CODE>Y #= 3</CODE> being propagated, which causes Y to be intantiated to 3
thus rendering the tentative value (2) irrelevant.<BR>
<BR>
Now the constraint <CODE>Y #\= Z</CODE>, is in conflict since Y is now 3 and Z has the
tentative value 3 as well. The constraint starts to propagate and removes 3
from the domain of <CODE>Z [1..2]</CODE>. <BR>
<BR>
As a result Z becomes a conflict variable since its tentative value (3)
is no longer in its domain. The <CODE>Y #\= Z</CODE> constraint remains in the
conflict constraint set because Z has no valid tentative assignment.<BR>
<BR>
The constraint <CODE>Y #\= X</CODE> is not affected, it neither goes into conflict
nor is its fd-version ever activated.<BR>
<BR>
To repair the remaining conflicts and to find actual solutions,
the <CODE>repair/0</CODE> predicate described below could be used.<BR>
<BR>
<A NAME="toc87"></A>
<H3 CLASS="subsection"><A NAME="htoc156">10.6.2</A>&nbsp;&nbsp;Repair Labeling</H3>
<A NAME="labeling"></A>
This is an example for how to use the information provided by the repair
library to improve finite domain labeling.
<A NAME="@default402"></A>
You can find the repair/1 predicate in the 'repairfd' library file.
<BLOCKQUOTE CLASS="quote"> <PRE CLASS="verbatim">
repair(ConflictSet) :-
    ( conflict_vars([C|_]) -&gt;       % label conflict
        indomain(C),                %  variables first
        repair(ConflictSet)
    ; conflict_constraints(ConflictSet, [C|_]) -&gt;
        term_variables(C, Vars),    % choose one variable in
        deleteffc(Var,Vars, _),     %  the conflict constraint
        Var tent_get Val,
        (Var = Val ; fd:(Var #\= Val)),
        repair(ConflictSet)
    ;                               % no more conflicts:
        true                        % a solution is found.
    ).
</PRE></BLOCKQUOTE>
The predicate is recursive and terminates when there are no more variables
or constraints in conflict.<BR>
<BR>
Repair search often finishes without labeling all variables, a
solution has been found and a set of tenable variables are still
uninstantiated. Thus even after the search is finished, Repair library
delayed goals used for monitoring constraints will be present in
anticipation of further changes.<BR>
<BR>
To remove them one has to ground these tenable variables to their
tentative values.<BR>
<BR>
Note that the example code never changes tentative values.
This has the advantage that this is still a complete, monotonic and
cycle-free algorithm.
However, it is not very realistic when the problem is difficult and
the solution is not close enough to the initial tentative assignment.
In that case, one would like to exploit the observation that it is often
possible to repair some conflict constraints by changing tentative
values. During search one would update the tentative values to be as
near as pssible to what one wants while maintaining consistency. If the
search leads to a failure these changes are of course undone.<BR>
<BR>
<HR>
<A HREF="libman069.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman064.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
</BODY>
</HTML>
